package com.xiaoyu.sort.basic;

import java.util.Arrays;

/**
 * @program: DS_and_A
 * @description: 简单插入排序
 * @author: YuWenYi
 * @create: 2021-04-28 22:43
 **/
public class InsertSort {

    public static void insertSort(int[] arr){
        int insertNum;
        int insertIndex;
        for (int i = 1; i < arr.length; i++) {  //i插入数的位置,从0开始无意义,因此从1开始与0作比较
            insertNum = arr[i];
            insertIndex = i-1;  //假设要插入的索引值为插入值的索引-1
            //如果要插入的数字小于要插入的位置的索引上的位置,那么就让该位置上的值让出位置
            //然后循环如此,最后得到插入数字最后应该插入的位置
            while (insertIndex >= 0 && arr[insertIndex] > insertNum){
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            arr[insertIndex+1] = insertNum;
        }
/*
        分步解析:
        int theInsertNum = arr[1];
        int theInsertIndex = 1-1;
        //theInsertIndex >= 0防止数组越界
        while (theInsertIndex >= 0 && arr[theInsertIndex] > theInsertNum){
            //如果满足arr[theInsertIndex] > theInsertNum,就将该位置的值后移
            arr[theInsertIndex + 1] = arr[theInsertIndex];
            theInsertIndex--;
        }
        arr[theInsertIndex+1] = theInsertNum;  //因为上面进行了--操作,因此需要+1回到该位置

        int theInsertNum1 = arr[2];
        int theInsertIndex1 = 2-1;
        //theInsertIndex >= 0防止数组越界
        while (theInsertIndex1 >= 0 && arr[theInsertIndex1] > theInsertNum1){
            //如果满足arr[theInsertIndex] > theInsertNum,就将该位置的值后移
            arr[theInsertIndex1 + 1] = arr[theInsertIndex1];
            theInsertIndex1--;
        }
        arr[theInsertIndex1+1] = theInsertNum1;  //因为上面进行了--操作,因此需要+1回到该位置*/
    }

    public static void main(String[] args) {
        int[] arr = new int[]{-9,-2,-17,4,6,-20,9,8,-16,50,4,15};
        int[] nums = new int[]{0,1,4,2,3,4};
        //insertSort(arr);
        //System.out.println(Arrays.toString(arr));
        //速率测试
        int[] bigData = new int[80000];
        for (int i = 0; i < 80000; i++) {
            bigData[i] = (int)(Math.random() * 80000);
        }
        long start = System.currentTimeMillis();
        insertSort(bigData);
        long stop = System.currentTimeMillis();

        System.out.println((stop-start)/1000.0);  //1秒不到即可完成,速度更快
    }
}
